// https://leetcode.cn/problems/minimum-absolute-difference-in-bst/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 利用BST中序遍历有序性质计算最小差值
// 2. 使用DFS中序遍历，记录前驱节点值
// 3. 比较当前节点与前驱节点的差值，更新最小值
// 4. 时间复杂度：O(N)，空间复杂度：O(H)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
private:
    int ret;
    int prev;

    void dfs(TreeNode* root)
    {
        if (root == nullptr)
        {
            return ;
        }

        dfs(root->left);
        if (prev != -1)
        {
            ret = min(ret, abs(root->val - prev));
        }
        prev = root->val;
        dfs(root->right);

        return ;
    }
public:
    int getMinimumDifference(TreeNode* root) 
    {
        prev = -1, ret = 0x3f3f3f3f;
        dfs(root);
        return ret;
    }
};

int main()
{
    vector<string> nodes1 = {"4","2","6","1","3"};
    vector<string> nodes2 = {"1","0","48","null","null","12","49"};
    Solution sol;

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    cout << sol.getMinimumDifference(root1) << endl;
    cout << sol.getMinimumDifference(root2) << endl;

    return 0;
}